package com.lichong;

public class Code02_Binary {
    /**
     * 普通的二分查找
     * @param arr
     * @param num
     * @return
     */
    public static boolean binarySearch(int[] arr,int num){
        if (arr==null||arr.length==0){
            return false;
        }
        int left = 0 ;
        int right = arr.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if (arr[mid]==num){
                return true;
            }else if(arr[mid]>num){
                right=mid-1;
            }else{
                left = mid+1;
            }
        }
        return false;
    }
    /**
     * 有序数组中找到大于等于num最左元素的索引，找到返回对应索引，否则返回-1
     * @param arr
     * @param num
     * @return
     */
    public static int theLeftNoLessNum(int[] arr ,int num){
        if (arr==null||arr.length==0){
            return -1;
        }
        int index = -1;
        int left = 0;
        int right = arr.length-1;
        while (left<=right){
            int mid = (left+right)/2;
            if (arr[mid]>num){
                right=mid-1;
                index=mid;
            }else {
                left=mid+1;
            }
        }
        return index;


}
    /**
     * 找到一个局部最小值对应索引即可。局部最小值定义：有一个数组，相邻元素不相等。如果以下三种情况满足其一即可：
     * 1.最左元素小于它第右边紧邻元素；2.最右元素小于它左边紧邻元素 3.非1、2情况，即小于它左侧元素，又小于其右侧元素
     *
    */
     public static int localMinimum(int[] arr) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int len = arr.length;
    if (arr[0] < arr[1]) {
        return 0;
    } else if (arr[len - 1] < arr[len - 2]) {
        return len - 1;
    }
    int left = 0;
    int right = len - 1;
    while (left < right-1) {
        int mid = (left+right)/2;
        if(arr[mid]<arr[mid-1]&&arr[mid]<arr[mid+1]){
            return mid;
        }else {
            if (arr[mid]>arr[mid-1]){
                right = mid-1 ;
            }else {
                left = mid +1;
            }
        }
    }
    return arr[left]<arr[right]?left:right;

}



}
